package com.exercises;

import com.alibaba.fastjson.JSONObject;

import java.util.*;

class ExerciseOffer38 {
    public static void main(String[] args) {
        StringBuilder s = new StringBuilder("1");
        System.out.println(JSONObject.toJSON(permutation("123")));
    }


    public static String[] permutation(String s) {
        Set<String> set = dfs(s);
        return set.toArray(new String[]{});
    }

    public static Set<String> dfs(String s) {
        Set<String> set = new HashSet<>();
        if (s.length() == 1) {
            set.add(s);
        } else {
            String leftOne = s.substring(0, 1);
            String rightSome = s.substring(1, s.length());
            Set<String> subSet = dfs(rightSome);
            for (String subStr : subSet) {
                for (int i = 0; i <= subStr.length(); i++) {
                    StringBuilder stringBuilder = new StringBuilder(subStr);
                    stringBuilder.insert(i, leftOne);
                    set.add(stringBuilder.toString());
                }
            }
        }
        return set;
    }

}
